/*
 Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.


Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
Sample Input
6
8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
 */
package com.yuan.algorithms.practice201506;

import java.util.Scanner;

public class 素数环 {

	static int[] result;
	static boolean[] mark;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = 1;
		while (sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println("Case " + num + ":");
			num++;
			result = new int[n];
			result[0] = 1;
			mark = new boolean[n + 1];
			f(n, 1);
			System.out.println();
		}
	}

	/**
	 * 递归计算素数环
	 * 
	 * @param n
	 *            素数环的长度
	 * @param current
	 *            当前位置
	 */
	private static void f(int n, int current) {
		if (current >= n) {
			for (int i = 0; i < result.length; i++) {
				if (i == result.length - 1) {
					System.out.println(result[i]);
				} else {
					System.out.print(result[i] + " ");
				}
			}
			return;
		}
		for (int i = 2; i <= n; i++) {
			if (mark[i]) {
				continue;
			}
			if (current != n - 1) {
				if (judge(i + result[current - 1])) {
					result[current] = i;
					mark[i] = true;
					f(n, current + 1);
					mark[i] = false;
				}
			} else {
				if (judge(i + result[current - 1]) && judge(i + result[0])) {
					result[current] = i;
					mark[i] = true;
					f(n, current + 1);
					mark[i] = false;
				}
			}
		}
	}

	/**
	 * 判断素数
	 * 
	 * @param n
	 * @return
	 */
	private static boolean judge(int n) {
		if (n % 2 == 0 && n != 2) {
			return false;
		} else {
			for (int i = 3; i <= Math.sqrt(n); i += 2) {
				if (n % i == 0) {
					return false;
				}
			}
		}
		return true;
	}

}
